package kruskal;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import java.util.LinkedList;

/*
计算严格次小生成树 
测试数据
7 11
0 1 5
0 2 7
0 6 2
1 3 9
1 6 3
2 4 8
3 5 4
4 2 8
4 5 5
4 6 4
5 6 6
*/
public class Main {
	static int n,m;
	static edge[] bian;
	//并查集判断是否形成环
	static int[] fa;
	//记录最大值和次大权值
	static long[][] dis1,dis2;
	//记录该边是否在mst中
	static int[] st;
	//与点i相连的点
	static int[] son;
	//对于点i来说最后一条描述他充当父节点的边
	static int[] now;
	//idx的上一条边
	static int[] pre;
	//记录idx边的权值
	static long[] wi;
	//记录第几条边
	static int idx;
	
	//最小生成树的邻接矩阵
	static long mst[][];
	//dfs中是否访问过
	static int[] visited;
	//dfs结束标记
	static boolean enddfs;
	
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		son=new int[m*2+1];
		pre=new int[m*2+1];
		now=new int[m*2+1];
		wi=new long[m*2+1];
		dis1=new long[n+1][n+1];
		dis2=new long[n+1][n+1];
		st=new int[m+1];
		bian=new edge[m];
		fa=new int[n+1];
		
		mst = new long[n+1][n+1];
		
		for(int i=1;i<=n;i++) {
			fa[i]=i;
		}
		for(int i=0;i<m;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			long c=sc.nextInt();
			if(a==b) {
				bian[i]=new edge(a, b, Long.MAX_VALUE);
				continue;
			}
			bian[i]=new edge(a, b, c);
			add(a, b, c);
			add(b, a, c);
		}
		
		System.out.println(kruskal());
		
		//打印mst
        for(int i=0;i<n+1;i++) {
        	for(int j=0;j<n+1;j++) {
        		System.out.printf("%5d", mst[i][j]);
        	}
        	System.out.println();
        }
        
        //dfs获取两个节点间的路径
        visited = new int[n+1];
        enddfs = false;
        LinkedList<Integer> path = new LinkedList<Integer>();
        path.add(2);//添加初始点
        dfs(2,3,path);
        
      
	}
	
	static int find(int x) {
		if (fa[x]!=x) {
			fa[x]=find(fa[x]);
		}
		return fa[x];
	}
	
	static void merge(int x,int y) {
		int a=find(x);
		int b=find(y);
		if (a!=b) {
			fa[a]=b;
		}
	}
	
	static long kruskal() {
		long ans=0;
		int cnt=0;
		Arrays.sort(bian,new Comparator<edge>() {
			@Override
			public int compare(edge a0, edge a1) {
				// TODO Auto-generated method stub
				if (a0.weight==Long.MAX_VALUE) {
					return 1;
				}else if (a1.weight==Long.MAX_VALUE) {
					return -1;
				}
				return (int) (a0.weight-a1.weight);
			}
		});
		for(int i=0;i<bian.length;i++) {
			int x=find(bian[i].sta);
			int y=find(bian[i].to);
			long c=bian[i].weight;
			//没形成环
			if (x!=y) {
				cnt++;
				fa[x]=y;
				st[i]=1;
				ans+=c;
				//输出边
				System.out.println(bian[i]);
				//MST的邻接表
				mst[bian[i].sta][bian[i].to] = bian[i].weight;
				mst[bian[i].to][bian[i].sta] = bian[i].weight;
			}
		}	
		
		return ans;
		//在最小生成树构成的图中依次遍历每个顶点，求出最小生成树中任意两个顶点所通过的路径的最大值dis1[u][v] 和 dis2[u][v]
		/*for(int i=1;i<=n;i++) {
			dfs(i, -1, 0, 0, dis1[i], dis2[i]);
		}
		long res=Long.MAX_VALUE;
		for(int i=0;i<m;i++) {
			//该边在mst中
			if (st[i]==1) {
				continue;
			}
			int u=bian[i].sta;
			int v=bian[i].to;
			long w=bian[i].weight;
			if (u==v) {
				continue;
			}
			if (w>dis1[u][v]) {
				res=Math.min(res, ans+w-dis1[u][v]);
				//防止最大权值和mst中的边权值相等
				//如果相等则减去次大权值
			}else if (w>dis2[u][v]) {
				res=Math.min(res, ans+w-dis2[u][v]);
			}
		}
		if (res==Long.MAX_VALUE) {
			return -1;
		}else {
			return res;
		}*/
	}
	
	static void add(int u,int v,long w) {
		//当前边的端点
		son[++idx]=v;
		//上一次u点所连的边
		pre[idx]=now[u];
		//更新u点最后一次连的边
		now[u]=idx;
		//保存边权值
		wi[idx]=w;
	}
	
	//dfs计算MST两个节点之间的路径，
	static void dfs(int sta,int des,LinkedList<Integer> path) {
		if(enddfs)
			return;
		//标记为已访问
		visited[sta] = 1;
		
		//查找和sta有链接的节点
		for(int i=0;i<n;i++) {
			if(mst[sta][i]!=0&&visited[i]!=1) {
				//判断是否到达目标节点
				if(i==des) {					
					path.add(i);
					enddfs = true;
					//输出路径数据
					//根据path里的数据找最大和次大
					while(!path.isEmpty()) {
						System.out.println(path.poll());
					}
				}else {
					//继续查找节点
					path.add(i);
					dfs(i,des,path);
					//回溯
					if(!path.isEmpty())
						path.removeLast();	
				}
			}
		}
				
	}
	
	
	//u为更新的当前点,flag为当前边的另一个顶点，max1最大权值，max2次大权值，d1记录最大权值，d2记录次大权值
//	static void dfs(int u,int flag,long max1,long max2,long d1[],long d2[]) {
//		d1[u]=max1;
//		d2[u]=max2;
//		for(int i=now[u];i>0;i=pre[i]) {
//			//该边连接的另一个点
//			int v=son[i];
//			//边的权值
//			long w=wi[i];
//			//避免进入当前边所连的顶点
//			if (v!=flag) {
//				long x=max1,y=max2;
//				if (w>max1&&w>d1[v]) {
//					//更新最大值和次大权值
//					y=max1;
//					x=w;
//					dfs(v, u, x, y, d1, d2);
//
//				}else if (w!=x&&w>max2&&w>d2[v]) {
//					if (d1[v]!=0) {
//						x=d1[v];
//					}
//					y=w;
//					dfs(v, u, x, y, d1, d2);
//				}
//			}
//		}
//	}
}	
class edge{
	int sta;
	int to;
	long weight;
	public edge(int sta, int to, long weight) {
		super();
		this.sta = sta;
		this.to = to;
		this.weight = weight;
	}
	@Override
	public String toString() {
		//边信息
		return String.format("<%d,%d> w=%d", this.sta,this.to,this.weight);
	}
	
}
